/*
https://leetcode.cn/problems/number-of-digit-one/submissions/582861498/
数字1的个数
数位dp
*/

class Solution {
public:
    int countDigitOne(int n) {
        if (n < 1) {
            return 0;
        }

        long di = 1;
        int h=n/10,cur=n%10,l=0;
        int res=0;

        while (h!=0||cur!=0) {
            if (cur==0) {
                res+=h*di;
            }
            else if (cur==1) {
                res+=h*di+l+1;
            }
            else {
                res+=(h+1)*di;
            }

            l+=cur*di;
            cur=h%10;
            h/=10;
            di*=10; 
        }

        return res;
    }
};
